1. Field of the Invention
The present invention relates to a method and apparatus for encoding a digital image and a method and apparatus for decoding an encoded digital image.
2. Description of the Related Art
Digital images have been utilized at increasingly more opportunities due to the widespread proliferation of the Internet and digital still cameras. However, digital images have large data sizes and therefore involve data compression for preservation and for use in communications. JPEG (Joint Photographic Experts Group) format is widely known as a general image compression format. JPEG format, which has been globally standardized, is now regarded as an indispensable compression scheme for handling digital images. JPEG-2000 (ISO/IEC 15444-1 or ITU-T Recommendation T.800) format has been standardized as a global standard for a next-generation image compression scheme which will substitute for JPEG. JPEG-2000 improves the image quality at lower bit rates, as compared with conventional JPEG, as well as supports lossless and lossy compressions, improve the ease of handling for an extensive progressive function and the like, and is therefore expected for proliferation in the future. However, JPEG-2000 format entails more complicated computations and a larger number of arithmetic operations than JPEG. Therefore, when a JPEG-2000 codec is implemented in hardware or in software, the resulting processing speed is necessarily lower than JPEG.
FIG. 1 illustrates the configuration for performing the processing associated with JPEG-2000 format. When image or picture data is compressed in accordance with JPEG-2000 format, the processing is performed in order from the left block to the right block. Conversely, for decompressing data compressed in accordance with JPEG-2000 into an image, the processing is performed in order from the right block to the left block in FIG. 1.
During compression processing, image data chromatically converted in color conversion unit 1 is wavelet-transformed by discrete wavelet transform unit 2 to generate wavelet coefficients. The generated wavelet coefficients are quantized by quantization unit 3, and then, a context and a bit (i.e., a bit to be compressed) used in next arithmetic encoding unit 5 are determined for each bit plane in coefficient bit modeling unit 4. Arithmetic encoding unit 5 encodes the bits using the context determined by coefficient bit modeling unit 4, and encoded data is rearranged in accordance with a prescribed format in code order control unit 6 to generate a JPEG-2000 code stream.
During decompression processing, on the contrary, code data is extracted from a JPEG-2000 code stream, and a bit is decoded by arithmetic encoding unit 5 using a context determined by coefficient bit modeling unit 4. Coefficient bit modeling unit 4 then determines data for each of bit planes that make up wavelet coefficients using the decoded bit. The decoded bit is further used for generating a context for decoding the next bit. After data of all bit planes have been decoded, decoded data is inverse quantized in quantization unit 3. Subsequently, the inverse-quantized data is inverse-wavelet-transformed in discrete wavelet transform unit 2 for transformation into image data. The transformed data is chromatically converted in color conversion unit 1 to eventually reproduce an image.
For description on detailed processing of JPEG-2000, refer to ISO/IEC 15444-1 or ITU-T Recommendation T.800.
In FIG. 1, coefficient bit modeling unit 4 and arithmetic encoding unit 5 process the wavelet coefficients generated through the wavelet transform and quantization on a bit-by-bit basis for each bit plane. This processing entails an immense amount of computational operations, and can be speeded by efficiently performing these operations. The following description will be centered on coefficient bit modeling processing performed by coefficient bit modeling unit 4.
Wavelet coefficients generated by applying the wavelet transform and quantization to image or picture data are divided into coding units called “code blocks,” such that the encoding processing is performed in units of code blocks. After one code block is processed, the next code block is processed. The size of the code block is restricted to some degree by JPEG-2000 standard, and in general, a 64×64 code block (64 pixels in the horizontal direction and 64 pixels in the vertical direction) or a 32×32 code block is mainly used in the encoding processing. The coefficient bit plane processing and arithmetic encoding are also performed in units of the code blocks. Each wavelet coefficient in a code block is processed in order from a higher rank bit plane. Specifically, at the time the topmost bit plane of the wavelet coefficients has been encoded within a code block, the next bit plane is encoded. This processing is repeated until a predetermined lower rank bit plane. Within a bit plane, as shown in FIG. 2, first encoded are four coefficients (P0, P32, P64, P96) in the vertical direction, and next encoded are four coefficients (P1, P33, P65, P97) to the right of the encoded coefficients in the horizontal direction. When four coefficients (P31, P63, P95, P127) at the right end of the code block have been processed, the coordinate in the horizontal direction returns to the left end of the code block, and the processing proceeds to the next four coefficients (P128, P160, P192, P224), advanced by four in the vertical direction. In this way, coefficients are encoded in the bit plane.
In the coefficient bit modeling processing, a context and a bit to be compressed are generated for each bit plane using one of three passes: a significance propagation pass, a magnitude refinement pass, and cleanup pass. Here, the context refers to a value which is generated in accordance with the state around a coefficient to be compressed, and is used in arithmetic encoding.
In the significance propagation pass (hereinafter called the “SIG pass”), when there is a coefficient which is not significant (i.e., the coefficient is insignificant), but is surrounded by eight peripheral neighboring coefficients, at least one of which is significant, this coefficient is processed in the significance propagation pass. A significant coefficient, herein used, refers to a coefficient which has been processed on a bit plane higher than a current bit plane, or the bit plane itself, in which “1” has already appeared. When a coefficient is subjected to the processing of the SIG pass, the state around the coefficient of interest is monitored to generate context CX in accordance with a context generating rule of the SIG pass, and the value of the current bit plane associated with that coefficient is designated as bit D of interest to be compressed. For details on the context generating rule, see specifications of JPEG-2000. This context CX is used to encode bit D of interest in the arithmetic encoding processing. After bit D of interest has been encoded, a sign bit indicative of positive or negative of this coefficient is encoded when bit D of interest is “1.” Also, when bit D of interest is “1,” this coefficient is handled as a significant coefficient from then on.
In the magnitude refinement pass (hereinafter called the “REF pass”), the processing is performed on a coefficient which has already been significant in a bit plane higher than the current bit plane. Here, a coefficient which becomes significant in a bit plane currently under processing is not included in coefficients to be processed. When a coefficient is subjected to the processing of the REF pass, the state around the bit of interest is monitored to determine whether or not a coefficient has become significant in a bit plane immediately above the current bit plane, and context CX and bit D to be compressed are generated and arithmetically encoded.
In the cleanup pass (hereinafter called the “CLN pass”), coefficients which have not been processed in the SIG pass or REF pass are subjected to the processing of the CLN pass, and context CX and bit D to be compressed are generated and arithmetically encoded.
The three passes are processed in the order of the SIG pass, REF pass, and CLN pass. After the processing in the respective passes has been performed for an entire code block, a transition is made to the processing in the next pass. Therefore, in the coefficient bit modeling, the pass is searched three times for each bit plane. As such, an immense number of calculations are required. Also, during the decompression processing, bits decoded by the arithmetic encoding must be referenced to determine the next pass and context CX, making it more difficult to perform the decompression processing at higher speeds than the compression processing.
Japanese Patent Laid-open Application No. 2003-032493 (JP, P2003-032496A) discloses an image encoding apparatus based on JPEG-2000 which comprises a plurality of bit plane generators each for slicing image data every bit plane and reading the sliced image data, and a plurality of encoders each for independently encoding data of each read bit plane, for purposes of reducing a computing time and saving a memory capacity.
Japanese Patent Laid-open Application No. 2003-087571 (JP, P2003-087571A) discloses a JPEG-2000-based image encoding apparatus which comprises coefficient bit modeling means for modeling conversion coefficients in a code block in order to reduce the encoding of a useless cleanup pass. The modeling means has detecting means for detecting a conversion coefficient which has not been encoded in a significance propagation pass and/or a magnitude refine pass, and encoding means for encoding a conversion coefficient detected by the detecting means in a cleanup pass.
Japanese Patent Laid-open Application No. 2003-101951 (JP, P2003-101951A) discloses an imaging apparatus which comprises a plurality of image compressing means which support different image compression schemes. In the imaging apparatus, imaging data is compressed by parallel processing of the image compressing means and is stored in the form of different compressed image files on a storage medium.
Japanese Patent Laid-open Application No. 2003-153228 (JP, P2003-153228A) discloses a JPEG-2000-based image encoding apparatus which has means for separating and extracting an encoded code stream to be encrypted from encoded code streams for preventing an increase in the data amount after encryption, encrypting means for encrypting the extracted encoded code stream, and means for writing the encrypted data back into the original encoded code stream at the same position.
FIG. 3 illustrates blocks for performing the processing involved in the coefficient bit modeling and arithmetic encoding when data is decompressed. Code data is supplied to arithmetic encoder 10 which generates decoded data. In this event, a context generated by the coefficient bit modeling processing is used in the arithmetic encoding. The context is generated by one of SIG pass context generator 12, REF pass contest generator 13, and CLN pass context generator 14.
First, SIG pass context generator 12 determines whether or not the data is subjected to a SIG pass. When the data is subjected to the SIG pass, the context is supplied to arithmetic coder 10. When the data is not subjected to the SIG pass, SIG pass context generator 12 determines whether or not the next data is subjected to the SIG pass without supplying any data to arithmetic coder 10. When SIG pass context generator 12 has processed the current code block in the current bit plane, REF pass context generator 13 next determines whether or not data is subjected to a REF pass. When the data is subjected to the REF pass, REF pass context generator 13 supplies a context calculated thereby to arithmetic coder 10. When the data is not subjected to the REF pass, REF pass context generator 13 determines whether or not the next data is subjected to the REF pass. After REF pass context generator 13 has processed the current code block in the current bit plane, CLN pass context generator 14 finally generates a context for data subjected to a CLN pass. After CLN pass context generator 14 has processed the current code block in the current bit plane, a transition is made to the processing for the next bit plane, causing SIG pass context generator 12 to again perform the processing.
Pass selector 11 selects a currently processed pass, and switches to the next pass each time the processing has been terminated in one pass. Memory 15 stores information on the state of each coefficient for the current code block, i.e., whether a coefficient is significant, whether this is the first REF pass, whether the coefficient has been processed, and the like, and is referenced and/or updated as required in the processing of each pass. Decoded data is also supplied to a corresponding context generator for generating next context CX.
As will be understood from the operations of the foregoing blocks, since the respective passes are processed in sequence, a long time is necessarily required for the processing.